'''
@Author: shj
@Date: 2020-05-31 17:22:42
@LastEditTime: 2020-05-31 17:58:40
@LastEditors: shj
@Description:  矩形覆盖
@FilePath: /python3/algorithms/offer_code/10_rectangle_cover.py
'''
'''
题目描述
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

比如n=3时，2*3的矩形块有3种覆盖方法： 
    (1)                  (2)                (3)
-------------       -------------       -------------
1   1   1   1       1   1       1       1       1   1
1   1   1   1       1   1-------1       1-------1   1
1   1   1   1       1   1       1       1       1   1
-------------       -------------       -------------

'''
'''
思路（递归）

n = 1 的时候
    只能横着覆盖，一种
n = 2 的时候
    可以横着和竖着覆盖，两种
n = 3 的时候
    第三级横着覆盖，用了一级，剩下 n = 2，有两种覆盖方法
    第三季竖着覆盖，用了两级，剩下 n = 1，有一种覆盖方法
    总共有 3 种
n = 4 的时候
    第 4 级横着覆盖，用了一级，剩下 n = 3，有三种覆盖方法
    第 4 级竖着覆盖，用了两级，剩下 n = 2，有两种覆盖方法
    总共有 5 种方法
n = n 的时候
    第 n 级横着覆盖，用了一级，剩下 n = n - 1，所以关注第 n - 1 种有几种覆盖方法
    第 n 级竖着覆盖，用了两级，剩下 n = n - 2，所以关注第 n - 2 种有几种覆盖方法
    总和为两种情况的总和
'''


class Solution:
    def rectCover(self, number):
        # write code here
        if number <= 2:
            return number
        # 排除用掉的1、2级
        (a, b) = (1, 2)
        # 递归
        for _ in range(number - 2):
            (a, b) = (b, a + b)

        return b


# test
sl = Solution()
a = sl.rectCover(4)
print(a)